package week6;

/**
 *
 * 221. 最大正方形
 * https://leetcode-cn.com/problems/maximal-square/
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：6 ms, 在所有 Java 提交中击败了64.39% 的用户
 * 内存消耗：41.8 MB, 在所有 Java 提交中击败了13.35% 的用户
 * 通过测试用例：73 / 73
 * 炫耀一下:
 *
 *
 */
public class Week6MaximalSquare {

    public int maximalSquare(char[][] matrix) {
        int maxSide = 0;
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            // 如果 二维数组 其中一个维度为空 则不处理
        } else {
            int rowLength = matrix.length;
            int columnLength = matrix[0].length;
            // 存储每个 矩阵点的最大值
            int[][] dynamicPlan = new int[rowLength][columnLength];
            for(int rowSize = 0; rowSize < rowLength; rowSize++) {
                for(int columnSize = 0; columnSize < columnLength; columnSize++) {
                    if(matrix[rowSize][columnSize] == '1') {
                        // 矩阵点 为 1 时 处理最大值
                        if(rowSize == 0 || columnSize == 0) {
                            dynamicPlan[rowSize][columnSize] = 1;
                        } else {
                            int left = dynamicPlan[rowSize - 1][columnSize];
                            int up = dynamicPlan[rowSize][columnSize - 1];
                            int opposite = dynamicPlan[rowSize - 1][columnSize - 1];
                            // 当前矩阵点最大边值 = min(左, 上, 斜角(左上) )  + 1
                            dynamicPlan[rowSize][columnSize] = Math.min(Math.min(left, up), opposite ) + 1;
                        }
                        // 获取 全局最大边
                        maxSide = Math.max(maxSide, dynamicPlan[rowSize][columnSize]);
                    }
                }
            }
        }


        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }
}
